package com.leetcode.algorithm.y22.m09.w2;

/**
 * 738. 单调递增的数字
 * 
 * https://leetcode.cn/problems/monotone-increasing-digits/
 * 
 * @author jie.deng
 *
 */
class Question0738Solution01 {

	public int monotoneIncreasingDigits(int n) {
		// 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
		// 全局最优：得到小于等于N的最大单调递增的整数。
		String str = String.valueOf(n);
		int len = str.length();
		char[] arr = str.toCharArray();
		int idx9 = len;
		for (int i = len - 1; i >= 1; i--) {
			if (arr[i - 1] - arr[i] > 0) {
				arr[i - 1] = (char) (arr[i - 1] - 1);
				idx9 = i;
			}
		}
		for (int i = idx9; i < arr.length; i++) {
			arr[i] = '9';
		}
		return Integer.parseInt(String.valueOf(arr));
	}

}